import java.util.*;

/**
 * 矩阵图
 */
public class matrixGraph {
    private char[] arrayV;//储存顶点
    private int[][] matrix;//存放权值和边
    private boolean isDirect;

    public matrixGraph(int x, boolean isDirect) {
        arrayV = new char[x];
        matrix = new int[x][x];
        this.isDirect = isDirect;
    }

    //传入顶点
    public void initV(char[] chars) {
        //初始化V
        for (int i = 0; i < arrayV.length; i++) {
            arrayV[i] = chars[i];
        }
        //初始话矩阵
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(matrix[i], Const.MAX);
        }
    }

    //插入边
    public boolean addEdge(char strV, char endV, int weight) {
        //要先找到对应的下标
        int indexStrV = getIndex_V(strV);
        int indexEndV = getIndex_V(endV);
        if (indexEndV == -1 || indexStrV == -1) {
            return false;
        }
        return addEdgeByIndex(indexStrV, indexEndV, weight);
    }

    private boolean addEdgeByIndex(int indexStrV,int indexEndV,int weight) {
        //将对应位置的值置为weight就是加上边了
        if (isDirect) {
            matrix[indexStrV][indexEndV] = weight;
        } else {//无向图是对称的 那么就对应的都要修改
            matrix[indexEndV][indexStrV] = weight;
            matrix[indexStrV][indexEndV] = weight;
        }
        return true;
    }
    private int getIndex_V(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if (arrayV[i] == v) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 广度优先遍历
     * 使用队列储存v对应的节点
     * @param v 从这里开始遍历 一层一层的比哪里
     */
    public void bfs(char v) {
        int str = getIndex_V(v);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(str);//将对应的节点放入队列
        boolean[] visited = new boolean[arrayV.length];//记录打印过的字符
        while (!queue.isEmpty()) {
            //将元素出出去，然后打印
            int index = queue.poll();
            System.out.print(arrayV[index] + " -> ");
            visited[index] = true;//说明这个节点打印了
            // 若没有那么就会现v重复打印，因为并没有将他置为ture 以后还会加入到队列中
            //遍历这个点，看他有那些边，并加入到队列中
            for (int i = 0; i < arrayV.length; i++) {
                if (matrix[index][i] != 0 && !visited[i]) {//说明这是个边 且没有被打印
                    queue.offer(i);
                    visited[i] = true;//放入到这个队列中就代表他已经打印了
                }
            }
        }
    }

    /**
     * 深度优先遍历
     */
    public void bfsDeep(char v) {
        int indexV = getIndex_V(v);
        boolean[] visited = new boolean[arrayV.length];
        bfsDeepChild(indexV, visited);
    }

    /**
     * 最小生成树
     * 克鲁斯卡尔最小生成树
     * 全局最优贪心算法
     * 先按边的权值来建立一个最小根堆,堆储存的是该边的起点的终点和权值，每次都取最顶的最小权值边建立树
     * 为防止有圈的生成，那么使用并查集来记下创建树的集合，这样就可以避免环的生成
     */
    public int kruskal(matrixGraph minTree) {
        PriorityQueue<edge> stack = new PriorityQueue<>(new Comparator<edge>() {
            @Override
            public int compare(edge o1, edge o2) {
                return o1.weight - o2.weight;
            }
        });
        UnionFindSet ufs = new UnionFindSet(1);
        //遍历真个矩阵表
        for (int i = 0; i < matrix.length; i++) {//str
            for (int j = 0; j < matrix[0].length; j++) {//end
                if (matrix[i][j] != 0) {
                    edge tmp = new edge(i, j, matrix[i][j]);
                    stack.add(tmp);
                }
            }
        }
        int size = 0;
        int totalWeight = 0;
        //不为空进入
        while (!stack.isEmpty()) {
            edge tmpE = stack.poll();
            if (!ufs.isUnion(tmpE.str, tmpE.end)) {//如果不是一个集合的，那么才插入到这树中
                minTree.addEdgeByIndex(tmpE.str, tmpE.end, tmpE.weight);
                ufs.union(tmpE.str, tmpE.end);
                totalWeight += tmpE.weight;
                size++;
            } else {
                //说明是一个在一个集合中，如果要插入的要那么就会成个环
                System.out.print("is circle  ");
            }
        }
        if (size == arrayV.length - 1) {
            return totalWeight;
        }
        return -1;
    }

        private void bfsDeepChild(int index, boolean[] visited) {
        //打印这个点 然后置为true表示已经打印了这个字符
        System.out.print(arrayV[index] + " -> ");
        visited[index] = true;
        for (int i = 0; i < arrayV.length; i++) {//遍历这个字符的边 要是没有被打印那么就给递归然后打印
            if (!visited[i] && matrix[index][i] != 0) {
                bfsDeepChild(i, visited);
            }
        }
    }

    /**
     * prim(普利姆)算法
     * 局部最优最小树算法
     * 有俩个集合，一个集合Y储存的是最小的树，另一个集合X储存的是没有放入的顶点
     * 每次都选初始顶点的最小边放入Y集合中，然后从X集合中去除，这样的好处就是可以
     * 避免最最小树成为一个环
     */
    public int prim(matrixGraph minTree, char chV) {
        int indexV = getIndex_V(chV);
        Set<Integer> treeSet = new HashSet<>();//最小树顶点
        Set<Integer> matrixSet = new HashSet<>();//所有的顶点
        int m = arrayV.length;
        //月色再皎洁 不是为了胸中丘壑
        treeSet.add(indexV);//将初始的节点放入到
        for (int i = 0; i < m; i++) {
            if (i != indexV) {
                matrixSet.add(i);
            }
        }

        PriorityQueue<edge> minHeap = new PriorityQueue<>(new Comparator<edge>() {
            @Override
            public int compare(edge o1, edge o2) {
                return o1.weight - o2.weight;
            }
        });

        //加入heap中的是最起始节点周围的边
        for (int i = 0; i < matrix[indexV].length; i++) {
            if (matrix[indexV][i] != 0 && !treeSet.contains(i)) {
                edge min = new edge(indexV, i, matrix[indexV][i]);
                minHeap.offer(min);
            }
        }

        int totalWeight = 0;
        int size = 0;
        //每次加的都是起始周围最小的边
        while (!matrixSet.isEmpty()) {
            edge min = minHeap.poll();
            int str = min.str;//起始位置就是他  是起始的indexV
            //但若是先前的边权值小于该起始位置的，那么取出来的就可之前的边
            int end = min.end;
            int weight = min.weight;
            if (matrixSet.contains(end)) {//说明这个顶点没有被加入到最小队中
                minTree.addEdgeByIndex(str, end, weight);
                System.out.println(arrayV[str] + "-> " + arrayV[end] + " : " + matrix[str][end]);
                size++;

                totalWeight += weight;
            } else {
                //加入的话就会形成环
            }
            treeSet.add(end);
            matrixSet.remove(end);

            //在新节点处再次加入堆
            for (int i = 0; i < m; i++) {
                if (matrix[end][i] != 0 && !treeSet.contains(i)) {//要最终的树不含有这个顶点
                    edge tmp = new edge(indexV, i, matrix[end][i]);
                    minHeap.offer(tmp);
                }
            }
        }

        if (size == m - 1) {
            return totalWeight;
        } else {
            return -1;
        }
    }

    /**
     * dijkstra算法 单源最小路径算法
     * 从起点开始，吧和其点最近的先放到dist数组中，然后进行松弛操作，若如果找到了比这更短的距离
     * 那么就更新这个顶点的距离
     * 他不能处理有负权值的情况
     * @param vSrc  起始的顶点
     * @param dist  迪杰斯特拉数组 存放的是到该点的最小距离
     * @param pPath 存放最小路径的路径
     */
    public void dijkstra(char vSrc, int[] dist, int[] pPath) {
        int initIndexV = getIndex_V(vSrc);
        //初始化数组
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(pPath, -1);

        //到自己距离为0
        dist[initIndexV] = 0;
        //路径初始话为自己
        pPath[initIndexV] = initIndexV;
        int n = dist.length;
        boolean[] isAdd = new boolean[n];
        //跟新n次dist数组的数值
        for (int i = 0; i < n; i++) {
            int min = Integer.MAX_VALUE;
            int str = initIndexV;
            //这里是找到最小的路径，然后在对这个最小路径进行松弛操作
            //当每次都找的是最小的路径时，在后面松弛操作时修改的最短路径才是正确的
            for (int j = 0; j < n; j++) {
                if (!isAdd[j] && dist[i] < min) {
                    //最小的距离的顶点的下标
                    str = j;
                    //更新最小的距离
                    min = dist[i];
                }
            }
            isAdd[str] = true;
            //松弛操作 遍历最小的这个顶点的边，找到看是否有到dist中储存的距离的更小的距离 有的话就给更新
            // 可能最小顶点会有n条边
            for (int j = 0; j < n; j++) {
                //这个节点没有被添加过且他到起点的权值大于从str到j的权值，那么就修改他的权值
                if (!isAdd[j] && matrix[str][j] != 0
                        && matrix[str][j] + dist[str] < dist[j]) {
                    dist[j] = matrix[str][j]+dist[str];//他储存的是直接到该顶点的最短据里
                    pPath[j] = str;//j指向这个str顶点，到时候可一直接通过他就找到最终的initIndex
                    // 这样就记录了这一条支路
                }
            }
        }
    }

    /**
     * @param c     起点顶点
     * @param dist  迪杰斯数组
     * @param pPath 路径数组
     */
    public void printShortPath(char c,int[] dist, int[] pPath) {
        int str = getIndex_V(c);
        int n = pPath.length;
        for (int i = 0; i < n; i++) {//遍历整个数组，打印出路径
            List<Character> list = new ArrayList<>();
            int index = i;
            while (index != str) {
                list.add(arrayV[index]);
                index = pPath[index];
            }
            list.add(c);
            //是从终点指向的起点，所以要翻转链表
            Collections.reverse(list);
            for (int j = 0; j < list.size(); j++) {
                System.out.print(list.get(j) + " -> ");
            }
            System.out.println(dist[i]);
        }
    }

    /**
     *  bellmanFord 贝尔曼—福特 单源最短路算法
     *  能解决负权值的问题，比迪杰斯特拉算法更暴力，他不去找最小的顶点，而是直接遍历所以的顶点
     *  然后找到最小路径 先遍历整个dist数组，然后在对数组中存在的顶点d1，遍历d1存在所有边，
     *  将更小的边更新与dist数组中
     * @param vSrc 起点
     * @param dist 距离储存
     * @param pPath 路线储存
     * @return 是否存在负权回路
     */
    public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) {
        int initIndexV = getIndex_V(vSrc);
        Arrays.fill(dist, Integer.MAX_VALUE);
        pPath[initIndexV] = initIndexV;
        dist[initIndexV] = 0;
        int n = dist.length;
        //遍历n个顶点
        for (int i = 0; i < n; i++) {
            //遍历dist数组中的顶点
            for (int j = 0; j < n; j++) {
                //没有储存距离的就不用遍历了
                if (dist[j] == Integer.MAX_VALUE) {
                    continue;
                }
                for (int k = 0; k < n; k++) {//遍历顶点的边的顶点，如果到达这里比原来的小那么就改变
                    //如果直接到k的距离大于从j在到k，那么就更新dist[k]的距离
                    if (matrix[j][k] != 0 && dist[k] > dist[j] + matrix[j][k]) {
                        dist[k] = dist[j] + matrix[j][k];
                        pPath[k] = j;//让终点k储存j的下标
                    }
                }
            }
        }
        //检查是否存在负权回路的情况 如果还能更新就说明有负权回路
        //因为从a->a的距离本该是0 但是入过存在负权回路，就会发现转一圈回来距离为负了，这显然是错的
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 0 && dist[j] > matrix[i][j] + dist[i]) {
//                    System.out.println("存在负权回路");
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * floydWarShall 弗洛伊德-沃歇尔 多源最短路算法，计算所有顶点的最短路径的算法
     * dist是个二维数组，他的y储存的是起始顶点位置，x储存的是到每个节点的最短路径
     * 设 D(i,j)从i->j的最短路径就是（1……endIndex）这个区间的节点为中间节点k所连接成的
     * 路径，那么就有：
     * 当存在k使i -> j为最小距离 --  D(i,j) = D(i,k)+D(k,j);
     * 若不存在k 那么就是  D(i,j)
     * 所以在开始时要先把dist数组中的值初始化为矩阵中的值，然后以每个顶点为中间节点k
     * 在遍历起始节点i和i的边的顶点j来找到最小的距离D(i,j)
     * @param dist
     * @param pPath
     */
    public void floydWarShall(int[][] dist,int[][] pPath) {
        //初始化
        for (int[] a1 : dist) {
            Arrays.fill(a1, Integer.MAX_VALUE);
        }
        int n = dist.length;
        //遍历整个矩阵，将初始距离放入打dist数组 dist[i][j] 表示从i -> j的距离
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                    pPath[i][j] = -1;
                } else if (matrix[i][j] != 0) {//存在边
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;//指向起点i
                } else {
                    //这里没有边
                    pPath[i][j] = -1;
                }
            }
        }

        //这里就要寻找最短路径了 以每个顶点k为中间节点来找最小值
        for (int k = 0; k < n; k++) {//k为中间节点 向后遍历dist去寻找最短的路径
            for (int i = 0; i < n; i++) {//这时起始节点
                for (int j = 0; j < n; j++) {//遍历所有边,以k为中点 找到到dist[i][j]的最短的路径
                    if (dist[i][k] != Integer.MAX_VALUE
                            &&dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                        //存在 i->k 和 k->j 且 i->k + k->j < i->j
                        //dist已经初始化过了，不需要matrix数组了 表示从i->j 距离大于从i->k->j
                        dist[i][j] = dist[i][k] + dist[k][j];
                        pPath[i][j] = pPath[i][k];//将终点j指向中点k j->k
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(dist[i][j] == Const.MAX) {
                    System.out.print(" * ");
                }else{
                    System.out.print(dist[i][j]+" ");
                }
            }
            System.out.println();
        }
        System.out.println("=========打印路径==========");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(pPath[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("=================");
    }

    public static void main7(String[] args) {
        testGraphFloydWarShall();
    }

    public static void testGraphFloydWarShall() {
        String str = "12345";
        char[] array = str.toCharArray();
        matrixGraph g = new matrixGraph(str.length(),true);
        g.initV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);
        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarShall(dist,parentPath);
        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
        }
    }

    public static void main6(String[] args) {
        testGraphBellmanFord();
    }
    public static void testGraphBellmanFord() {
        String str = "syztx";
        char[] array = str.toCharArray();
        matrixGraph g = new matrixGraph(str.length(),true);
        g.initV(array);
//    g.addEdge('s', 't', 6);
//    g.addEdge('s', 'y', 7);
//    g.addEdge('y', 'z', 9);
//    g.addEdge('y', 'x', -3);
//    g.addEdge('z', 's', 2);
//    g.addEdge('z', 'x', 7);
//    g.addEdge('t', 'x', 5);
//    g.addEdge('t', 'y', 8);
//    g.addEdge('t', 'z', -4);
//    g.addEdge('x', 't', -2);
//负权回路实例
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('y', 's', 1);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', -8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean flg = g.bellmanFord('s', dist, parentPath);
        if(flg) {
            g.printShortPath('s', dist, parentPath);
        }else {
            System.out.println("存在负权回路");
        }
    }
        public static void main5(String[] args) {
        testGraphDijkstra();
    }
    public static void testGraphDijkstra() {
        String str = "syztx";
        char[] array = str.toCharArray();
        matrixGraph g = new matrixGraph(str.length(),true);
        g.initV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.dijkstra('s', dist, parentPath);
        g.printShortPath('s', dist, parentPath);
    }




    public static void main4(String[] args) {
        matrixGraph m = new matrixGraph(4, true);
        int[][] arr = {{1, 2}, {0, 1}, {2, 0}};
        List<Integer> l = m.remainingMethods(3, 2, arr);
        System.out.println("stop");
    }

    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<Integer> list = new LinkedList<>();
        UnionFindSet ufs = new UnionFindSet(n);//表示安全顶点和不安去顶点的关系
        Set<Integer> set = new HashSet<>();//储存存在的边
        //添加边 并吧有问题的顶点放入set中去
        for (int i = 0; i < n; i++) {
            //直接调用和间接调用
            ufs.union(invocations[i][0], invocations[i][1]);
            //回去重的
            set.add(invocations[i][0]);
            set.add(invocations[i][1]);
        }
        List<Integer> root = ufs.getRoot();
        int[] ufsArr = ufs.getArr();
        int index = k;
        int size = 0;
        while (root.size() == 1 && ufsArr[index] >= 0) {
            index = ufsArr[index];
            size++;
        }
        if (size == n-1) {
            return list;
        }
        if (root.size() == 1 && root.get(0) != k) {//只有一个根且顶点不为k说明都不能删
            for (Integer i : set) {//遍历所有顶点
                list.add(i);
            }
            return list;
        }else {
            for (Integer i : set) {//遍历所有顶点
                if (!ufs.isUnion(k, i)) {//不和k是一个集合的擦加入
                    list.add(i);
                }
            }
            return list;
        }
    }


    public void showMatrix() {
        for (int[] ints : matrix) {
            for (int v : ints) {
                if (v == Const.MAX) {
                    System.out.print(0+"  ");
                }else {
                    System.out.print(v + "  ");
                }
            }
            System.out.println();
        }
    }
    public static void testGraphMinTreePrim() {
        String str = "abcdefghi";
        char[] array = str.toCharArray();
        matrixGraph g = new matrixGraph(str.length(), false);
        g.initV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        matrixGraph primTree = new matrixGraph(str.length(), false);
        System.out.println(g.prim(primTree, 'a'));
        primTree.showMatrix();
    }

    public static void main3(String[] args) {
//        testGraphMinTreePrim();
    }

    public static void testGraphMinTree() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        matrixGraph g = new matrixGraph(str.length(),false);
        g.initV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        matrixGraph kminTree = new matrixGraph(str.length(),false);
        System.out.println(g.kruskal(kminTree));
        kminTree.showMatrix();
    }

    public static void main2(String[] args) {
//        testGraphMinTree();
        testGraphMinTreePrim();
    }

    public static void testBfS() {
        matrixGraph graph = new matrixGraph(4,true);
        char[] array = {'A','B','C','D'};
        graph.initV(array);
        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);
        graph.bfs('B');
    }
    public static void main1(String[] args) {
        matrixGraph m = new matrixGraph(4, false);
        char[] chars = {'A', 'B', 'C', 'D'};
//        testBfS();
        m.initV(chars);
        m.addEdge('A', 'B', 1);
        m.addEdge('A', 'D', 1);
        m.addEdge('B', 'A', 1);
        m.addEdge('B', 'C', 1);
        m.addEdge('D', 'A', 1);
        m.addEdge('D', 'C', 1);
//        m.showMatrix();
        m.bfsDeep('A');

        System.out.println("stop");
    }
}







